package org.sanguine.study.hometasks.second;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Task18 {
	
	/**
	 * Find maximum rectangle (sub-matrix) of given value in matrix
	 * @param given matrix
	 * @param value of finding rectangle
	 * @return array of int = {left low corner's column, left low corner's row, up right corner's column, up right corner's row}
	 * or null if given value is not present in matrix or matrix is not rectangle.
	 * Point of (0,0) is low left corner of given matrix and Point of (MaxColumn, MaxRow) is Up right corner of matrix
	 * 
	 *  Using David Vandevoorde's Algorithm (O(n*m))
	 *  
	 *  // Variables to keep track of the best rectangle so far: best_ll = (0, 0; best_ur = (-1, -1)
	 *  // M - number of rows, N - number of columns
	 *	// The cache starts with all zeros: 
	 *	c[0 .. M-1] = 0 // One extra element (closes all rectangles)
	 *	define update_cache(x) 
   	 *		for y = 0 .. M-1 
     * 			if b[x, y]!=0 
     *    			c[y] = c[y]+1 
     * 			else 
     *    			c[y] = 0 
	 *
	 *	define area(11, ur) 
   	 *		if 11.x>ur.x or 11.y>ur.y // If ur is left of or 
     * 			return 0               // below 11: return 0 
   	 *		else 
     * 			return (ur.x-11.x+1)*(ur.y-11.y+1)
	 *	
	 *	main algorithm: 
   	 *		for x = N-1 .. 0 
     *			update_cache(x)
     * 			width = 0 // Width of widest opened rectangle 
     * 			for y = 0 .. M 
     *    			if c[y]>width // Opening new rectangle(s)? 
     *       			push(y, width)
     *       			width = c[y] 
     *    			if c[y]<width // Closing rectangle(s)? 
     *       			do 
     *         				(y0, w0)= pop()
     *         				if width*(y-y0)>area(best_ll, best_ur)
     *           				best_ll = (x, y0)
     *             				best_ur = (x+width-1, y-1)
     *         				width = w0 
     *       			until c[y]>=width 
     *       			width = c[y] 
     *       			if width!=0 // Popped an active "opening"? 
     *          			push(y0, width)
	 *   
	 */
	
	public static int[] findMaximumRectangleForValue(int[][] matrix, int value) {
		if (!checkMatrix(matrix, value)) return null;
		
		int[] bestRectangle = new int[]{0, 0, -1, -1};
		
		int M = matrix.length;
		int N = matrix[0].length;
		
		int[] cache = new int[M + 1];
		int width;
		Stack<int[]> stack = new Stack<>();
		
		for (int x = N - 1; x >= 0; x--) {
			updateCache(matrix, value, cache, x);
			width = 0;
			for (int y = 0; y <= M; y++) { ///TODO check!!!!
				if (cache[y] > width) {
					stack.push(new int[]{y, width});
					width = cache[y];
				}
				if (cache[y] < width) {
					int y0;
					do {
						int[] pair = stack.pop();
						y0 = pair[0];
						if (width * (y - y0) > calcArea(bestRectangle)) {
							bestRectangle[0] = x;
							bestRectangle[1] = y0;
							bestRectangle[2] = x + width - 1;
							bestRectangle[3] = y - 1;
						}
						width = pair[1];
					} while (!stack.isEmpty() && cache[y] < width);
					width = cache[y];
					if (width != 0) stack.push(new int[]{y0, width});
				}
			}
		}
		return bestRectangle;
	}

	private static boolean checkMatrix(int[][] matrix, int value) {
		if (matrix == null) return false;
		
		int rowLength = matrix[0].length;
		
		for (int i = 0; i < matrix.length; i++)
			if (matrix[i] == null || matrix[i].length != rowLength) return false;
			else
				for (int j = 0; j < rowLength; j++)
					if (matrix[i][j] == value) return true;
		
		return false;
	}

	private static void updateCache(int [][] matrix, int value, int[] cache, int x) {
		for (int y = 0; y < cache.length - 1; y++)
			if (matrix[y][x] == value) cache[y]++;
			else cache[y] = 0;
	}

	private static int calcArea(int[] rectangle) {
		if (rectangle[1] > rectangle[3] || rectangle[0] > rectangle[2]) return 0;
		return (rectangle[2] - rectangle[0] + 1) * (rectangle[3] - rectangle[1] + 1);
	}
	
	/**
	 * Find maximum rectangle (sub-matrix) of identical elements in given matrix
	 * @param given matrix
	 * @return array of int = {left low corner's column, left low corner's row, up right corner's column, up right corner's row}
	 * or null if matrix is not rectangle.
	 * Point of (0,0) is low left corner of given matrix and Point of (MaxColumn, MaxRow) is Up right corner of matrix
	 */
	
	public static int[] findMaximumRectangleOfIdenticalElements(int[][] matrix) {
		
		//find all different values in matrix then find the biggest rectangle from maximum rectangles of found values
		if (matrix == null) return null;
		
		Map<Integer, Integer> values = new HashMap<>();
		
		for (int i = 0; i < matrix.length; i++)
			if (matrix[i] != null) 
				for (int j = 0; j < matrix[i].length; j++) {
					Integer count = values.get(matrix[i][j]);
					if (count == null) values.put(matrix[i][j], new Integer(1));
					else values.put(matrix[i][j], ++count);
				}
			else return null;
		
		Integer[][] countAndValues = new Integer[values.size()][];
		
		int i = 0;
		for (Map.Entry<Integer, Integer> entry : values.entrySet())
			countAndValues[i++] = new Integer[]{entry.getValue(), entry.getKey()};
		
		values = null; //free memory of hashtable bucket structures
		
		Arrays.sort(countAndValues, new Comparator<Integer[]>() {

			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				return o2[0].compareTo(o1[0]); //reverse natural order by count
			}
			
		});
		
		int[] bestRectangle = null;
		int maxRectangleSize = 0;
		for (i = 0; i < countAndValues.length; i++) {
			int value = countAndValues[i][1];
			int[] rectangle = findMaximumRectangleForValue(matrix, value);
			if (rectangle != null) {
				int rectangleSize = calcArea(rectangle);
				if (bestRectangle == null || rectangleSize > maxRectangleSize) {
					bestRectangle = rectangle;
					maxRectangleSize = rectangleSize;
				}
				if (i < countAndValues.length - 1 && maxRectangleSize >= countAndValues[i + 1][0]) break;
			}
		}
		
		return bestRectangle;
	}
}
